/* Copyright (C) 2010  Romolo Camplani, Marco Fortunato, Marco Marelli, Guido Rota, Fabio A. Schreiber et al.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

package org.dei.perla.sys.hlqexecutor;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Permette la realizzazione di una struttura dati albero n-ario. 
 * Un albero è visto come un nodo che ha un nodo padre e n-sottoalberi. Ogni sottoalbero è sostanzialmente un albero.
 * Anche le foglie dell'albero sono pensata come alberi i cui sottoalberi sono nulli.
 * @author  Luigi Rinaldi
 */

public class Tree<T>{
	
	private Node<T> rootNode;
	
	/**
	 * Costruttore
	 * Genera un albero costituito da un solo nodo.
	 * @param obj l'oggetto generic T da memorizzare nel nodo.
	 */
	public Tree(T obj) {
		this.rootNode = new Node<T>(obj);
	}
	
	/**
	 * Costruttore
	 * Genera un albero constituito da un nodo che ha n-sottoalberi.
	 * @param obj obj l'oggetto generic T da memorizzare nel nodo.
	 * @param subTree n oggetti di tipo Tree da memorizzare come sottoalberi.
	 * @throws TreeException genera un'eccezzione se un subTree non è un albero valido.
	 */
	public Tree(T obj, Tree<T>... subTree) throws TreeException {
		this.rootNode = new Node<T>(obj);
		for(Tree<T> t:subTree){
			addSubTree(t);
		}
	}
	
	/**
	 * Costruttore
	 * Genera un albero constituito da un nodo che ha n-sottoalberi.
	 * @param obj obj l'oggetto generic T da memorizzare nel nodo.
	 * @param subTree un ArrayList di oggetti Tree da memorizzare come sottoalberi.
	 * @throws TreeException genera un'eccezzione se un subTree non è un albero valido.
	 */
	public Tree(T obj, ArrayList<Tree<T>> subTree) throws TreeException {
		this.rootNode = new Node<T>(obj);
		for(Tree<T> t:subTree){
			addSubTree(t);
		}
	}
	
	
	/**
	 * Permette di aggiungere un sott'albero all'albero.
	 * @param subTree l'oggetto TreeQuery da impostare come sott'albero.
	 * @throws TreeException lancia un'eccezzione se il sott'albero passato è gia presente
	 * nella struttura ad albero o se è già un sottoalbero di un nodo.
	 */
	public boolean addSubTree( Tree<T> subTree) throws TreeException {
		if(subTree.getRootNode().getParent() != null) throw new TreeException("The subtree have already a parent!");
		if(this.contains(subTree)) throw new TreeException("The tree is already subTree");
		
		
		boolean tmp = this.rootNode.setSubTree(subTree);
		if (tmp)
			subTree.getRootNode().setParent(this.getRootNode());
		return tmp;
    }
	
	/**
	 * Rimuove un sott'albero dall'albero.
	 * @param subTree l'oggetto TreeQuery da rimuovere dall'albero.
	 * @throws TreeException lancia un'eccezzione se il sott'albero passato non è presente
	 * nella struttura ad albero.
	 */
    public boolean removeSubTree(Tree<T> subTree) throws TreeException{
    	if(!contains(subTree)) throw new TreeException("The subTree isn't a subTree of this tree.");
    	if(this == subTree) throw new TreeException("The subTree isn't a subTree of this tree.");
    	
    	
    	boolean tmp = subTree.getRootNode().getParent().removeSubTree(subTree);
    	if(tmp)
    		subTree.getRootNode().setParent(null);
    	return tmp;
    }
    
    /**
     * Restituisce i sottoalberi dell'albero corrente.
     * @return un ArrayList di sottoalberi di tipo Tree.
     */
    public ArrayList<Tree<T>> getSubTree() {
    	return this.rootNode.getSubTree();
	}
    
    /**
     * Restituisce un iteratore di sottoalberi del nodo corrente.
     * @return un oggetto Iterator di sottoalberi.
     */
    public Iterator<Tree<T>> getSubTreeIterator() {
    	return this.rootNode.getSubTree().iterator();
	}
    
	
    /**
     * Verifica se un sott'albero fa parte dell'albero.
     * @param subTree l'oggetto TreeQuery di cui si vuol verificare la presenza.
     * @return un valore boolean che è vero se il subTree è stato trovato.
     */
    public boolean contains(Tree<T> subTree){
    	if(this == subTree)
    		return true;
    	for (Tree<T> t:this.rootNode.getSubTree())
    		if (t.contains(subTree))
    			return true;
    	return false;
    	
    }
    
    /**
     * Permette di avere una lista degli oggetti contenuti nelle foglie dell'albero.
     * @return un oggetto ArrayList di generic T che rappresentano le foglie dell'albero.
     */
    public ArrayList<T> getLeaf() {
    	ArrayList<T> tmp = new ArrayList<T>();
    	if (this.isLeaf())
    		tmp.add(this.getObject());
    	else
    		for(Tree<T> t:this.rootNode.getSubTree())
    			tmp.addAll(t.getLeaf());
    	return tmp;
    }
    
    /**
     * Permette di avere una lista dei sottoalberi foglie.
     * @return un oggetto ArrayList di Tree rapppresentanti i sottoalberi foglia.
     */
	public ArrayList<Tree<T>> getSubTreeLeaf(){
		ArrayList<Tree<T>> tmp = new ArrayList<Tree<T>>();
    	if (this.isLeaf())
    		tmp.add(this);
    	else
    		for(Tree<T> t:this.rootNode.getSubTree())
    			tmp.addAll(t.getSubTreeLeaf());
    	return tmp;
	}

	/**
	 * Permette di sapere se è la radice dell'albero.	 
	 * @return un boolean che restituisce vero se si tratta della radice dell'albero.
	 */
	public boolean isRoot() {
		return (this.rootNode.getParent() == null);
	}
	
	/**
	 * Permette di sapere se l'albero è in realta un sottoalbero foglia.
	 * @return un boolean che restituisce vero se l'albero stesso è una foglia.
	 */
	public boolean isLeaf() {
		return this.rootNode.getSubTree().isEmpty();
	}
	
	/**
	 * Ritorna il livello dell'albero.
	 * @return un int che rappresenta 0 in presenza del nodo radice 1 se si tratta di un figlio del nodo radice,
	 * e cosi via dicendo.
	 */
	public int getLevel() {
		return this.rootNode.getLevel();
	}
	
	/**
	 * Ritornato l'oggetto memorizzato nel nodo del corrente albero.
	 * @return un generic T memorizzato nella struttura.
	 */
	public T getObject() {
		return this.rootNode.getNode();
	}

	/**
	 * Ritorna il nodo dell'albero.
	 * @return il nodo dell'albero.
	 */
	private Node<T> getRootNode() {
		return this.rootNode;
	}
	
	
	
	/**
	 * Permette di iterare su un albero. Ritorna gli oggetti contenuti nei nodi dell'albero ordinati per livelli, a partire 
	 * dalle foglie fino ad arrivare al nodo radice. Riordina l'albero rispettando una sorta di dipendenza dati.
	 * @return un iteratore di oggetti generic T.
	 */
	public Iterator<T> nodeIterator() {
		return new TreeIterator<T>(this.clone());
	}

	
	/**
	 * Crea una copia esatta dell'oggetto tree.
	 * @return una copia dell'oggetto Tree.
	 */
	public Tree<T> clone() { 
		Tree<T> tmp = new Tree<T> (this.getObject());
		try {
			for(Tree<T> st : this.getSubTree())
				tmp.addSubTree(st.clone());
		} catch (TreeException e) {
			e.printStackTrace();
			return null;
		}
		return tmp;
	}
	

	/**
	 * Implementa un oggetto Nodo utile per organizzare i dati in una struttara ad albero n-ario. 
	 * ATTENZIONE: L'oggetto memorizzato nel nodo non viene restituito come copia e neppure il 
	 * il cotruttore non ne fa una copia. Questo oggetto non è visibile al di fuori di questa classe.
	 * @author  Luigi Rinaldi
	 */

	private class Node<G> {
	 
		private G obj;
		private Node<G> parent;
		private ArrayList<Tree<G>> subTrees;
		
		/**
		 * Costruttore
		 * Crea un nodo e inserisce all'interno di esso l'informazione.
		 * @param obj un oggetto generic G.
		 */
		Node(G obj) {
			this.setNode(obj);
			this.setParent(null);
			subTrees = new ArrayList<Tree<G>>() ;
		}
		
		/**
		 * Permette di impostare i sottoalberi di un nodo.
		 * @param subTree un oggetto Tree.
		 */
		boolean setSubTree(Tree<G> subTree) {
			return this.subTrees.add(subTree);
		}
		
		/**
		 * Rimuove un sottoalbero dal nodo.
		 * @param subTree un oggetto Tree.
		 */
		boolean removeSubTree(Tree<G> subTree) {
			return this.subTrees.remove(subTree);
		}
		
		/**
		 * Restituisce i sottalberi di un nodo.
		 * @return ArrayList di oggetti Tree.
		 */
		ArrayList<Tree<G>> getSubTree() {
			return this.subTrees;
		}

		/**
		 * Permette di settare il contenuto informativo del nodo. 
		 * @param obj un oggetto generic G
		 */
		void setNode(G obj) {
			this.obj = obj;
		}

		/**
		 * Restituisce il contenuto informativo di un nodo.
		 * @return un oggetto generic G.
		 */
		G getNode() {
			return this.obj;
		}
		
		/**
		 * Permette eventualmente di impostare un nodo padre.
		 * @param parent un oggetto generic G.
		 */
		void setParent(Node<G> parent) {
			this.parent = parent;
		}

		/**
		 * Permette di conoscere qual è il padre del nodo.
		 * @return un oggetto Node.
		 */
		Node<G> getParent() {
			return this.parent;
		}
		
		/**
		 * Fornisce informazioni sul livello del nodo. Restituisce 0 se si tratta di un nodo radice.
		 * @return un int.
		 */
		int getLevel() {
			if(this.parent == null)
				return 0;
			else 
				return 1 + this.parent.getParent().getLevel();
		}
	}

	
	/**
	 * Costruisce un iteratore che itera l'albero restituento ad ogni passo dell'terazione l'informazione contenuta nei nodi dell'albero.
	 * L'ordine in cui viene restituito l'insieme degli oggetti contenuti nell'albero è il seguente: restituisce gli oggetti in modo da 
	 * rispettare le dipendenze dati imposte dall'albero, ossia restituisce prima tutte le foglie, poi tutti padri delle foglie e 
	 * cosi via dicendo.
	 * @author  Luigi Rinaldi
	 */
	private static class TreeIterator<T> implements Iterator<T> {
		private int current;
		private T tmp;
		private ArrayList<T> listNode;
		
		/**
		 * Costruttore
		 * @param tree un oggetto Tree rappresentante l'albero da iterare.
		 */
		TreeIterator(Tree<T> tree){
			listNode = new ArrayList<T>();
			current = 0;
			buildArray(tree);
		}
		
		/**
		 * Riempie ArratList listNode con tutti gli oggetti contenuti all'interno dell'albero.
		 * La particolarità sta nel fatto che ordina gli oggetti negli array rispettando le dipendeze 
		 * dei vari nodi, ossia li ordina per livello a partire dalle foglie fino ad arrivare al 
		 * nodo radice. L'albero deve essere visto come una sorta di dipendenze dati a partire dal
		 * nodo radice. Le dipendenze dati sono nulle nelle foglie.
		 * @param tree un oggetto Tree.
		 */
		private void buildArray(Tree<T> tree) {
			if(tree == null)
				return;
			else {
				for(Tree<T> st: tree.getSubTreeLeaf()) {
					listNode.add(st.getObject());
					try {
						tree.removeSubTree(st);
					} catch (TreeException e) {
						e.printStackTrace();
					}
				}
				buildArray(tree);
			}
		}
		
		@Override
		public boolean hasNext() {
			return current+1==listNode.size();
		}

		@Override
		public T next() throws NoSuchElementException {
			if(!this.hasNext()) throw new NoSuchElementException("No element found");
			
			tmp = listNode.get(current);
			current++;
			return tmp;
		}

		@Override
		public void remove() {
			// TODO Non è necessario per il momento
		}
	}
}
